package hot100;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

public class Solution76 {

    public String minWindow(String s, String t) {
        Map<Character, Integer> originMap = new HashMap<>();
        Map<Character, Integer> countMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            originMap.put(t.charAt(i), originMap.getOrDefault(t.charAt(i), 0) + 1);
        }

        int left = 0;
        int right = -1;
        int minLen = Integer.MAX_VALUE;
        int ansLeft = -1;
        int ansRight = -1;
        while (right < s.length()) {
            right++;
            if (right < s.length() && originMap.containsKey(s.charAt(right))) {
                countMap.put(s.charAt(right), countMap.getOrDefault(s.charAt(right), 0) + 1);
            }
            while (equalMap(originMap, countMap) && left <= right) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    ansLeft = left;
                    ansRight = left + minLen;
                }
                if (originMap.containsKey(s.charAt(left))) {
                    countMap.put(s.charAt(left), countMap.getOrDefault(s.charAt(left), 0) - 1);
                }
                left++;
            }
        }
        return ansLeft == -1 ? "" : s.substring(ansLeft, ansRight);
    }

    public boolean equalMap(Map<Character, Integer> except, Map<Character, Integer> actual) {
        for (Entry<Character, Integer> next : except.entrySet()) {
            Character key = next.getKey();
            Integer value = next.getValue();
            if (actual.getOrDefault(key, 0) < value) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution76 solution76 = new Solution76();
        solution76.minWindow("ADOBECODEBANC", "ABC");

    }
}
